package linked_list

import "fmt"

// 定义节点
type Node struct {
	Data Elem
	Next *Node
}

// 单向循环链表
type CircularLinkedList struct {
	headNode *Node
	size     int
}

// 判断是否为空的
func (list *CircularLinkedList) IsEmpty() bool {
	return list.size == 0
}

// 长度
func (list *CircularLinkedList) Length() int {
	return list.size
}

//从头部添加元素
func (list *CircularLinkedList) Add(data Elem) *Node {
	node := &Node{Data: data}
	if list.IsEmpty() {
		list.headNode = node
		node.Next = list.headNode
	} else {
		lastNode := list.headNode
		// 找到最后一个节点
		for lastNode.Next != list.headNode {
			lastNode = lastNode.Next
		}
		lastNode.Next = node
		node.Next = list.headNode
		list.headNode = node
	}

	list.size++
	return node
}

//从尾部添加元素
func (list *CircularLinkedList) Append(data Elem) {
	node := &Node{Data: data}
	if list.IsEmpty() {
		list.headNode = node
		node.Next = list.headNode
	} else {
		lastNode := list.headNode
		// 找到最后一个节点
		for lastNode.Next != list.headNode {
			lastNode = lastNode.Next
		}
		lastNode.Next = node
		node.Next = list.headNode
	}

	list.size++
}

// 在指定位置添加元素
func (list *CircularLinkedList) Insert(index int, data Elem) {
	// 小于0,插入头部；大于链表长度,插入尾部
	if index <= 0 {
		list.Add(data)
	} else if index >= list.Length() {
		list.Append(data)
	} else {
		// 寻找index的前一个节点
		preNode := list.headNode
		count := 0
		for count < (index - 1) {
			preNode = preNode.Next
			count++
		}
		node := &Node{Data: data}
		node.Next = preNode.Next
		preNode.Next = node
	}
	list.size++
}

//删除指定位置的元素
func (list *CircularLinkedList) RemoveAt(index int) {
	if list.size == 0 {
		return
	} else if index > list.size-1 {
		panic("index is out of range")
		return
	}
	if list.size == 1 {
		list.headNode = nil
		list.size = 0
		return
	} else {
		var node, preNode *Node
		if index == 0 {
			preNode = list.Get(list.size - 1)
		} else {
			preNode = list.Get(index - 1)
		}
		node = preNode.Next
		preNode.Next = node.Next
		if index == 0 {
			list.headNode = preNode.Next
		}

		node.Next = nil
		node = nil
	}
	list.size--

}

//删除指定元素
func (list *CircularLinkedList) Remove(data *Node) bool {
	preNode := list.headNode
	for i := 0; i < list.size; i++ {
		if data.Data == preNode.Data {
			list.RemoveAt(i)
			return true
		}
		preNode = preNode.Next
	}
	return false
}

// 获取链表中的第i个元素
func (list *CircularLinkedList) Get(index int) *Node {
	preNode := list.headNode
	if index <= 0 {
		return preNode
	} else if index >= list.Length() {
		panic("index is out of range")
	} else {
		// 找到需要查找的节点
		for i := 0; i < index; i++ {
			preNode = preNode.Next
		}
	}

	return preNode
}

//遍历所有元素
func (list *CircularLinkedList) PrintList() {
	if !list.IsEmpty() {
		preNode := list.headNode
		for i := 0; i < list.size; i++ {
			fmt.Printf("\t%v", preNode.Data)
			preNode = preNode.Next
		}
		fmt.Println()
	}
}
